{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "e68fa287-e527-495b-9bb6-91d7101ecb49",
   "metadata": {},
   "source": [
    "# 基于知识图谱与图神经网络的菜品推荐方案\n",
    "\n",
    "杨凯伦，张兴浩，王飞龙\n",
    "\n",
    "导师：宫继兵\n",
    "\n",
    "燕山大学 信息科学与工程学院\n",
    "\n",
    "yangkailunysu@163.com\n",
    "\n",
    "# 摘要\n",
    "\n",
    "基于美团菜品数据搭建知识图谱，通过图神经网络的信息聚合能力学习用户与菜品的相似度从而实现用户个性化的召回。继而采用FFM与CatBoost模型利用用户购买菜品的上下文信息对推荐列表进行精排。最后集成三种模型的结果通过一个过滤补充层，过滤掉明显不符合要求的菜品，补充符合要求的菜品实现最终的Top-5推荐。通过调整流程中各种参数最终在测试集上的效果逐步提高。\n",
    "\n",
    "# 正文\n",
    "\n",
    "## 背景\n",
    "\n",
    "互联网的出现和普及在满足用户需求的同时带来了极大便利，与此同时，海量的商品及信息也给注意力有限的用户带来困扰。解决这类信息超载问题的一种有效方法是推荐技术，它可以根据用户的需求，兴趣，为用户推荐其可能感兴趣的商品或信息，已经成为学术界和工业界最为关注的研究问题之一。\n",
    "\n",
    "美团外卖作为国内主要的网上订餐平台之一，面对海量用户，如何在特定的时间地点下精准推荐感兴趣、合胃口的商家或菜品，方便用户解决用餐需求，提高用户用餐满意度，是一个值得长期探索的重要问题。相较于普通的电商推荐，外卖推荐具有用户属性多维，用户决策时间短，用户兴趣具有周期性等特点，这也给外卖推荐技术研究带来了更多挑战。\n",
    "\n",
    "我们团队注意到菜品，菜品商家之间存在自然的链接关系可以构成知识图谱，现在学术界对于图神经网络（GNN）的应用在推荐的研究也取得了许多进展。所以我们考虑利用图神经网络作为主模型实现用户的个性化菜品召回。同时我们注意到用户购买菜品时包含丰富的上下文信息，例如时间，价格，地点等。我们采用FFM和CatBoost融合这些上下文信息对召回的推荐列表进行了调整。\n",
    "\n",
    "## 任务来源和要求\n",
    "\n",
    "本次比赛使用美团外卖App用户订单行为构造数据集。数据集中包括了时间跨度为四周的1240419个订单行为，涉及200000个用户，29924个商家，195244件菜品，订单关联菜品数据共3915394条，构成外卖知识图谱。参赛选手需要根据前三周的实体及属性，关系，为最后一周的用户订单预测并推荐其可能感兴趣的商家或菜品。\n",
    "\n",
    "提交的预测结果会和真实订单结果比较，并根据HR[@5](https://github.com/5)(hit rate [@Top](https://github.com/Top) 5)评分。HR[@N](https://github.com/N)是目前Top-N推荐研究中十分流行的评价指标，计算方式为：\n",
    "\n",
    "$$\n",
    "HR = \\frac{\\#hits}{\\#users}\n",
    "$$\n",
    "\n",
    "其中#users是用户总数，而#hits是测试集中的item出现在Top-N推荐列表中的用户数量，本次竞赛取N=5。\n",
    "\n",
    "## 研究方案和内容\n",
    "\n",
    "![整体流程图](./SMP-spu.png)\n",
    "\n",
    "我们团队的整体推荐流程如上图所示。总体可分为三大阶段和一个策略调整层。\n",
    "\n",
    "### 召回阶段\n",
    "\n",
    "首先第一个阶段是召回层。由于总的菜品数量有接近20万。我们考虑到直接对20万的菜品进行个性化排序，一方面由于我们的主模型采用的是相对复杂的图神经网络模型，时间开销较大，调整参数不方便。另一方面，考虑所有的菜品排序需要更多精细的特征处理，特征工程相对耗时，也不方便快速搭建流程。综合上面的因素，我们通过简单的统计所有菜品中被购买的次数。分别召回最流行的2w，5w的菜品作为后续的模型排序和补充推荐的候选集。\n",
    "\n",
    "### 排序阶段\n",
    "\n",
    "其次第二阶段是排序阶段。我们采用了图神经网络的推荐模型作为主模型。对于知识图谱的构建，我们注意到菜品所属的商家是一种自然链接的知识图谱关系。我们进一步发现一个用户可能多次同时购买两种菜品。于是我们统计了所有用户的购买记录，形成一个两种菜品共同购买的次数的矩阵。然后我们考虑到如果两种菜品多次同时被购买，那么它们之间就存在很强的相关性。我们就创建一种关系表示这种共同的购买。我们这里设置了一个阈值是25。最后我们把上面两种知识图谱与用户购买菜品的二部图统一成一个图输入图神经网络中。\n",
    "\n",
    "我们实现的图神经网络参考了最新的图神经网络在推荐上的应用论文KGIN[<sup>1</sup>](#refer-anchor-1)模型。但是我们考虑到模型的复杂性导致参数调整的困难，去掉了原始论文中对于意图的建模。建模流程如下：\n",
    "\n",
    "首先对于所有的用户，菜品和知识图谱中的关系初始化表示向量$\\mathbf{e}_{i},\\mathbf{e}_{r},\\mathbf{e}_{v}$，其中$l$代表GNN卷积的层数，$\\mathcal{N}_{i}$代表菜品$i$的邻居关系和实体集合。\n",
    "$$\n",
    "\\mathbf{e}_{i}^{(l)}=\\frac{1}{\\left|\\mathcal{N}_{i}\\right|} \\sum_{(r, v) \\in \\mathcal{N}_{i}} \\mathbf{e}_{r} \\odot \\mathbf{e}_{v}^{(l-1)}\n",
    "$$\n",
    "\n",
    "通过上面的公式2，我们得到菜品经过一层信息聚合的向量表示。\n",
    "\n",
    "$$\n",
    "\\mathbf{e}_{u}^{(l)}=\\frac{1}{\\left|\\mathcal{N}_{u}\\right|} \\sum_{i \\in \\mathcal{N}_{u}} \\mathbf{e}_{i}^{(l-1)}\n",
    "$$\n",
    "\n",
    "公式3中的$\\mathcal{N}_{u}$代表用户$u$的邻居菜品集合，通过公式3我们得到$l$层的用户向量表示。\n",
    "\n",
    "$$\n",
    "\\mathbf{e}_{u}^{*}=\\mathbf{e}_{u}^{(0)}+\\cdots+\\mathbf{e}_{u}^{(L)}, \\quad \\mathbf{e}_{i}^{*}=\\mathbf{e}_{i}^{(0)}+\\cdots+\\mathbf{e}_{i}^{(L)}\n",
    "$$\n",
    "\n",
    "通过公式4，我们将多层卷积得到的用户和菜品向量加和，得到最终的用户向量表示$\\mathbf{e}_{u}^{*},\\mathbf{e}_{i}^{*}$。\n",
    "\n",
    "$$\n",
    "\\hat{y}_{u i}=\\mathbf{e}_{u}^{* \\top} \\mathbf{e}_{i}^{*}\n",
    "$$\n",
    "通过公式5，我们得到用户对菜品的评分$\\hat{y}_{u i}$。\n",
    "\n",
    "$$\n",
    "\\mathcal{L}_{\\mathrm{BPR}}=\\sum_{(u, i, j) \\in O}-\\ln \\sigma\\left(\\hat{y}_{u i}-\\hat{y}_{u j}\\right)\n",
    "$$\n",
    "\n",
    "$$\n",
    "\\mathcal{L}=\\mathcal{L}_{\\mathrm{BPR}}+\\lambda_{1}\\|\\Theta\\|_{2}^{2}\n",
    "$$\n",
    "\n",
    "优化过程如公式6，7所示，我们采用常用的BPR loss，负样本的选取我们随机从用户没有购买过的菜品中选取，比例为1：1。并添加$L_2$正则化项。\n",
    "训练完成后，我们对召回菜品的打分进行排序，得到了对每个用户推荐的50个菜品。我们提交结果获得了0.103的HR@5的结果。相比于Top-1的0.17还有较大差距。我们认为我们仅仅考虑了用户购买菜品的协同信号和菜品的共同购买和菜品的商家属性是远远不够的。赛题给出的数据中包含着丰富的上下文与属性信息。例如用户购买菜品发生在上午下午这种时间特征，用户购买菜品所属的收餐蜂窝id特征，用户的历史单均价，菜品的价格等。\n",
    "\n",
    "FM是经典的推荐算法，我们实验了它的效果以及它的变种算法FFM。结果表明FFM效果明显好于FM，这可能是因为FFM模型在FM模型的基础上引入了特征域的概念，在做特征交叉时，每个特征选择与其他域对应的隐向量做内积运算。\n",
    "\n",
    "FFM模型的实现我们采用了流行的机器学习框架xLearn[<sup>2</sup>](#refer-anchor-2)，xLearn 是一款高性能的，易用的，并且可扩展的机器学习算法库。\n",
    "\n",
    "FFM模型的输入特征包括用户id，菜品id，购买时间段（上午，下午等），购买时的aor，菜品属于的商家id，用户的历史购买价格区间类别，菜品价格的划分的区间类别。除菜品价格外，其他特征均是类别特征，我们进行了统一编码后没有进行其他处理。对于菜品的价格，我们进行了分桶处理将它转换成类别特征。最终的分桶数为7。训练时的负样本构造我们随机选取用户没有购买过的菜品，与正样本的比例为1：1。我们固定训练轮数为100，不设验证集。模型训练好后，针对GNN模型给用户推荐的50个菜品进行打分重新排序得到最终的输出。\n",
    "\n",
    "另外我们采用了CatBoost算法对GNN模型推荐的50个菜品进行调整排序。CatBoost[<sup>3</sup>](#refer-anchor-3)是一个常用的开源Boosting算法，与XGBoost和LightGBM类似。CatBoost是一种基于对称决策树算法的参数少、支持类别型变量和高准确性的GBDT框架，主要解决的问题是高效合理地处理类别型特征，同时处理梯度偏差以及预测偏移问题，提高算法的准确性和泛化能力。\n",
    "\n",
    "CatBoost模型的输入特征包括用户id,菜品id，购买时间段，购买时的aor，购买时的时间。其中对于购买时的时间，原始数据是日期的形式，我们按照时间先后处理为0，1，2…… 其他特征进行简单的类型编码。 负样本从用户未购买过的菜品中选取，比例为1：1。我们固定训练轮数为1000，不设验证集。模型训练好后，对GNN模型给每个用户推荐的50个菜品进行打分重新排序得到最终的输出。\n",
    "\n",
    "但是无论是经过FFM还是CatBoost的调整后的推荐结果，提交之后都没有获得超过GNN模型的HR@5效果。\n",
    "\n",
    "我们团队分析虽然单个模型的效果GNN最好，但是由于FFM，CatBoost模型学习的特征与GNN模型有不同，而且FFM，CatBoost模型的学习策略与GNN明显不同。GNN模型是基于协同过滤的方法，而FFM，CatBoost是基于点击率预估的方法。所以，FFM，CatBoost的结果一定反映了与GNN模型推荐不同的信息。现在的关键是如何融合三个模型各自的特点优势，提升效果。\n",
    "\n",
    "### 融合阶段\n",
    "\n",
    "通过调研，我们采用了简单的平均集成策略，这个策略是一种Bagging集成策略。由于在GNN模型中主要使用的是用户菜品的协同信息和菜品的共现信息，CatBoost中考虑了订单的购买时间信息，FFM考虑了用户和菜品的价格信息。可以看出三种模型使用的特征有所不同，从而对于集成来说各个模型有一定的独立性。\n",
    "\n",
    "另外，虽然GNN，CatBoost，FFM三个模型都有各自的输出评分，但是我们考虑到它们的数值范围和意义不同，没有采用直接相加取平均的策略。而是首先按照分数由低到高分别对三个模型的输出进行排序，根据排序我们重新计算每个菜品的一个排序得分s。\n",
    "\n",
    "$$\n",
    "s = \\frac{r-1}{50-1}\n",
    "$$\n",
    "\n",
    "其中r代表菜品的排序号，由于精排的菜品数是50，所以，r的范围是[1，50]。例如菜品a排在第一位，那么它的s=0；菜品b排在第50位，s=1。\n",
    "\n",
    "得到每个菜品在三个模型中的排序得分后，进行加权平均得到最终的集成得分。我们通过实验确定的三个模型的权值分别是$w_{GNN}=0.9，w_{FFM}=0.9，w_{CatBoost}$。经过集成调参后，我们获得了20%左右的效果提升，达到了0.120左右的HR@5的效果。\n",
    "\n",
    "### 过滤补充层\n",
    "\n",
    "最后我们设计了过滤补充层，这一想法来源于下面的一种直觉思考：如果要预测的订单发生在中午，日常生活中中午吃正餐的概率很大，但是我们的模型如果推给用户一份油条豆腐脑，这个明显是早餐的选择。那么我们的HR@5效果就会受到影响。\n",
    "\n",
    "基于上面的思考，我们统计了集成后推荐结果中没有在订单时间购买过的菜品，将它们删除，然后后面排序的菜品递补。在实现上这里我们采用了一个技巧，例如对于菜品的购买时间段，有中午，上午等五类，我们对于每个菜品定义一个长度为5的数组，初始化为0。在训练集中统计这种菜品购买的时间段，对应的数组位置加一。最后得到在各个时间段上总的购买次数，之后进行归一化生成一种概率表示。在使用这个数组过滤推荐列表中的菜品时，我们就可以设置[0，1)的一个阈值，从而灵活的选择过滤的数量。\n",
    "\n",
    "我们将这个策略应用到不同的特征，例如用户收餐蜂窝id，收餐地址aoi类型。\n",
    "\n",
    "经过实验，这样的过滤补充后，效果有所提升，HR@5到达0.123左右。\n",
    "\n",
    "上面的实现简单并且符合我们的直觉，而且相比于通过调整模型参数获得提升更加确定。受到这种思路的启发，我们顺着这个思路继续想下去。我们设想下面一种直觉：一种菜品例如可乐，它很少单独成为一个订单，而是作为一种搭配菜与其他的菜品进行凑单。因为我们可以得到预测的菜单中包含多少菜品，那么对于一个菜单只有一个菜品的情况，这时如果推荐可乐那么命中的概率将会受到影响。\n",
    "\n",
    "按照上面的思路，我们统计了训练集中每种菜品被购买时订单中包含的菜品数量，对于推荐列表中的一个菜品，我们对比这次订单包含的菜品个数n与菜品历史被购买菜单包含的菜品个数的最小值m。如果m>n，那么这个菜品将被过滤掉，递补其他菜品。\n",
    "\n",
    "经过上面的召回，排序，融合，过滤补充阶段后，我们获得了最好的HR@5结果0.133。\n",
    "\n",
    "## 试验结果\n",
    "\n",
    "| Model    | HR@5  |\n",
    "| -------- | ----- |\n",
    "| GNN      | 0.10  |\n",
    "| FFM      | 0.083 |\n",
    "| Catboost | 0.097 |\n",
    "| Ensemble | 0.120 |\n",
    "| Final    | 0.133 |\n",
    "|          |       |\n",
    "\n",
    "上表展示了整个流程中各个模块输出的效果对比。从中可以得到下面一些观察：\n",
    "\n",
    "* GNN的效果相比FFM，CatBoost的效果要好一些，说明GNN较好的捕捉了用户菜品之间的协同信息。\n",
    "* 集成（Ensemble）后的效果相比三个模型单独的效果提升了20%左右，说明这种简单的平均集成策略也有不错的效果。另一方面也说明GNN，FFM，CatBoost的结果具有一定的独立性，集成后降低了模型的方差，提高了模型的泛化能力。\n",
    "* 加入过滤补充层后（Final）的结果相比集成（Ensemble）的结果提升了10%左右，原因可能是由于目前的方案没有进行细致的特征工程，导致引入噪声，影响了前面模型的效果。通过过滤补充策略比较简单有效的弥补了这个缺点。\n",
    "\n",
    "## 技术关键点\n",
    "\n",
    "综合上面所述的方案和结果，本方案的关键技术点总结如下：\n",
    "\n",
    "* 精简后的GNN模型利用简单的知识图谱快速的从几万的菜品中生成大小为50的推荐列表。这里的关键是去掉了原始论文中对意图的复杂建模，提高了运行的效率，有利于快速验证效果。\n",
    "* 构建利用上下文信息的FFM和CatBoost模型，由于GNN模型没有捕捉用户购买时的上下文信息，例如时间，地点等。FFM，CatBoost在这方面做了很好的补充。结合后面的平均集成策略，实现了效果的较大提升。\n",
    "* 设置最后的过滤补充层，对模型推荐的菜品进行最后的调整。实验表明这种简单的过滤补充对于效果的提升也很明显。\n",
    "\n",
    "## 存在问题及改进方向\n",
    "\n",
    "得益于整个流程的搭建和精细的调参，我们的方案得到了现在的效果。但是我们的方案仍然是粗糙的，并有很多改进的方向。我们简单的总结如下：\n",
    "\n",
    "* 对于特征的分析和构建不足。整个方案我们的特征工程做的较少，这一方面是受制于我们的经验，另一方面是我们的策略考量，我们的策略是先搭建流程。作为一个改进方向，可以进一步构造GNN模型使用的知识图谱特征。构造更多特征从而更好的发挥FFM的特征交叉能力和CatBoost的特征选择能力。\n",
    "* GNN模型的使用过于简单，没有根据具体的应用场景进行一些定制化。例如其实我们一直想做建模用户菜品的复购率这个特征，但是实验没有成功，这个也是改进的一个方向。\n",
    "* 召回层的设计过于粗糙，本方案中采用了单一的流行度召回策略，没有考虑多路召回。这样对于一些冷启动的用户和物品的推荐效果不好。引入多路召回也是一个重点改进的方向。\n",
    "\n",
    "# 参考\n",
    "\n",
    "<div id=\"refer-anchor-1\"></div>\n",
    "[1] [Learning Intents behind Interactions with Knowledge Graph for Recommendation](https://arxiv.org/pdf/2102.07057v1.pdf)\n",
    "\n",
    "<div id=\"refer-anchor-2\"></div>\n",
    "[2] [xLearn](https://xlearn-doc-cn.readthedocs.io/en/latest/)\n",
    "\n",
    "<div id=\"refer-anchor-3\"></div>\n",
    "[3] [CatBoost](https://catboost.ai/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "a5d3fd46-4665-4856-86d9-00d75b2b6248",
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3 (ipykernel)",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.9.13"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}
